Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="sz7mYW5i5CUMNk8+" --sz7mYW5i5CUMNk8+ Content-Type: text/plain; charset="UTF-8" Content-Disposition: inline NIST's round-3 report claims a better FO proof picture for Kyber than it does for NTRU. This is wrong---exactly the opposite of what the literature says on this topic. Here's what the report says about FO proofs for Kyber: The security proofs hold tightly in the ROM [169, 170] and non-tightly in the QROM. Yet under various other natural assumptions, KYBER may also achieve a tight security reduction in the QROM [184]. Here's what the report says about FO proofs for NTRU: The NTRU KEMs have tight CCA-security reductions to the underlying PKEs in the ROM, and non-tight security reductions in the QROM. Making some additional non-standard assumptions, one of the QROM security proofs can be made tight. This portrays NTRU as having a worse security-proof picture than Kyber: NTRU needs "non-standard assumptions" for a tight QROM proof, whereas Kyber "may" have a tight QROM proof under "natural" assumptions. In fact, the situation for years has been that the literature has better FO proofs---better tradeoffs between tightness and the strength of the PKE assumption---for deterministic PKEs than for randomized PKEs: * ROM, deterministic PKE: https://eprint.iacr.org/2018/526 Theorem 14.3 obtains IND-CCA2 very tightly from the standard minimal PKE security assumption, OW-CPA. (The techniques are older, but this paper is designed to support proof verification and identifies errors in some previously claimed theorems.) * ROM, randomized PKE: https://eprint.iacr.org/2017/604 has a proof that's (almost as) tight, but assumes that the PKE is IND-CPA. IND-CPA is still standard, but it's stronger and more complicated than OW-CPA, and has received less attention from cryptanalysts. (See generally Section 6 of https://eprint.iacr.org/2019/691.) * QROM, deterministic PKE: https://eprint.iacr.org/2019/590 obtains IND-CCA2 tightly from OW-CPA. I'm assuming here that sqrt(epsilon) is allowed as tight, unlike a number-of-queries loss factor. * QROM, randomized PKE: All tight proofs in the literature make non-standard assumptions, such as the "disjoint simulatability" assumption from the paper [184] that NIST cites. This is stronger than standard assumptions; declaring that it's "natural" doesn't make cryptanalysis magically appear, and doesn't tell us whether the security levels are as high as desired. The Kyber PKE (like other GAM/LPR variants) is randomized, so it definitely can't use the better proofs. The NTRU PKE is deterministic (since round 2), so presumably the better proofs apply. Someone should check the details of this application, but the risk of an error here doesn't justify NIST making claims that are out of whack with the applicable literature. NIST's report thus needs an erratum to say that, oops, the report said that NTRU needs a "non-standard assumption" for a tight QROM proof and didn't say this about Kyber, whereas in fact the literature indicates that Kyber needs a non-standard assumption for a tight QROM proof while NTRU doesn't. If NIST _isn't_ allowing sqrt(epsilon) as "tight", then the report needs to clarify the "tight" dividing line. An erratum is still required for the misinformation that Kyber has a better FO proof picture than NTRU: in fact, Kyber has a worse FO proof picture than NTRU. This is important because this Kyber proof gap could be hiding a big security loss. See https://eprint.iacr.org/2021/912 for examples where FO IND-CCA2 security is far below OW-CPA security of the underlying PKE. This is exactly the "derandomization" risk described in Sections 3.8 and 5.8 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf, which was filed before NIST's deadline for round-3 input and which, unfortunately, NIST doesn't seem to have read. But simply reading through the previous FO proofs is sufficient to see that NIST's report gets this security comparison backwards. ---D. J. Bernstein P.S. This is unrelated to the objections that have been raised to the handling of hashing in Kyber's FO security proofs. Qualitatively, those objections are identifying an error in the proofs, which of course is worrisome in a security analysis that NIST's report calls "thorough". However, the idea that someone is going to find a collision in these hash functions is very far down any reasonable list of post-quantum security risks; and plugging in known indifferentiability results closes the proof gap at the expense of a quantitatively minor loss of tightness. Derandomization is a much bigger issue. P.P.S. Kyber has had a new version in every round, and presumably one should wait to see the next version before filing comments on it, so I'm filing this is a round-3 comment. However, unless there's a radical change in Kyber, I would expect the same comment to continue to apply. P.P.P.S. This comment is of course also regarding NTRU, which NIST's report says NIST could still select. The underlying issues are also applicable to the split between deterministic PKEs and randomized PKEs in other submissions, although unfortunately NIST's report is structured in a way that obfuscates such comparisons. -- You received this message because you are subscribed to the Google Groups "pqc-forum" group. To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov. To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20220727063151.345224.qmail%40cr.yp.to. --sz7mYW5i5CUMNk8+ Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEE3QolqQXydru4e4ITsMANTjsOVFkFAmLg29cACgkQsMANTjsO VFmF6BAAy6Bca5ZwyJpQSeE6xmhJ+knwxjqZrwZwtPKoq1gW/hLBr4Gs0KP1WgJM 8u4fqb5joKuo2ZZ62LhV+rqCSShbLq0zjqjlxwZCrl8rwcwqReixyMl3ydrHy2kC M2q8E6rUlN39N+FGu12Sozcm2Ki9yRGqC4mDVrUmvZ+2hh3XAKxGnfuJ4Zdk7qG7 hxkVkWxUTuLzIgAYgeSYWxrTcqR6EL1yuo+i9+UCtRPESXfIHLPIWdpUXDlClIwy /OWreF+h/llCdOpM0ehttYQ30GcbzlqKkXbyfhGmd/asROflr+8Bqnvk49tvpzVW UM4hBJ29LV4bjsYYuWkwsGMfFWwGnJvMn0QwSi/EhkfWHDMhzGdGjWrizNyukaI1 ZW6NMvzCqMSLgrzZzdeyVVm4l7Nge/mEwiIHmjOuo+qC3x6csz2JT9ktmys573iD H3Ta2HrcJkc1XjMlHmnfHS6N2MZkXmxNZsdf1wOHfs2PKxUoWk2rBpQBg5DO6h0i mvuQ0UR45gZqf5edNZShJ6RYqR0AMmN5riE+KeMg6FSjAAa0VgydJXQ58vbNfIIP HKYxhwB5AcjCC00g1NC5SMKIlISXrlfCc/N0X6zGy8oC58N2Cnn+QmDfjgmLjPa2 v3OHIgq432RwP86m/DDiq/0tLMHDZevgITMZ40hBQTpa2ZiQfis= =SIPP -----END PGP SIGNATURE----- --sz7mYW5i5CUMNk8+--